package com.github.hgkmail.hello.leetcode101.collection.deque;

import javafx.util.Pair;

import java.util.*;

//双端队列：double end queue -> deque
//deque常见操作：xxLast, xxFirst
//入队offer -> offerLast, offerFirst
//出队poll -> pollLast, pollFirst
//查看peek -> peekLast, peekFirst
public class LC239SlidingWindowMaximum {
    //使用优先队列（堆）
    //技巧：每次滑动，右边增加一个元素，放入优先队列；左边删除一个元素，除非这个元素是最大值，否则暂时不用管
    //java的pair：1.int[2] 2.javafx.util.Pair
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int len=nums.length;
        if (len<=0) {
            return new int[]{};
        }
        //PriorityQueue是小顶堆
        //Pair<nums[i], i>
        PriorityQueue<Pair<Integer, Integer>> heap = new PriorityQueue<>(len, new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                return o2.getKey() - o1.getKey(); //转成大顶堆
            }
        });
        int[] res = new int[len-k+1];
        for (int i = 0; i < k; i++) {
            heap.offer(new Pair<>(nums[i], i));
        }
        //右移，i是步数
        for (int i = 0; i < res.length; i++) {
            int winLeft = i;
            int winRight = i+k-1;
            if (i>0) { //步数大于0才新增元素
                heap.offer(new Pair<>(nums[winRight], winRight));
            }
            //最大值是否在窗口左边
            while (heap.peek().getValue()<winLeft) {
                heap.poll();
            }
            //当前最大值
            Pair<Integer, Integer> max = heap.peek();
            res[i] = max.getKey();
        }
        return res;
    }

    //单调递减队列解法：如果新的元素比旧的元素大，那么旧的元素可以抛弃，因为新的元素既大又在右边
    //队列入口：不断插入新元素，如果队尾元素比新元素小，则可以抛弃，直到队尾元素比新元素大（又旧又小的元素真可怜，完全没有成为最大值的机会）
    //队列出口：第一个元素就是最大的元素，但要检查它是否在窗口里面
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length<=0) {
            return new int[]{};
        }
        int[] res= new int[nums.length-k+1];
        //单调递减队列
        //Pair<nums[i], i>
        Deque<Pair<Integer, Integer>> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            //入队，丢弃又旧又小的元素
            while (!deque.isEmpty() && deque.peekLast().getKey() < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(new Pair<>(nums[i], i));
            //是否形成窗口了
            if (i>=k-1) {
                int winLeft=i-k+1;
                int winRight=i;
                while (!deque.isEmpty() && deque.peekFirst().getValue()<winLeft) {
                    deque.pollFirst(); //丢弃不在窗口内的最大元素
                }
                res[winLeft]=deque.peekFirst().getKey();
            }
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC239SlidingWindowMaximum().maxSlidingWindow2(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
    }
}
